import functools
from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def profitableSchemes(self, n: int, p: int, group: List[int], profit: List[int]) -> int:
        groups = [(group[i], profit[i]) for i in range(len(group))]
        groups.sort()
        size = len(groups)

        # 计算不考虑利润，只考虑人数的情况下的选择数
        # O(N×S)
        dp1 = [[1] * (n + 1) for _ in range(size + 1)]
        for i in range(size - 1, -1, -1):
            n1, p1 = groups[i]
            for j in range(n + 1):
                dp1[i][j] = dp1[i + 1][j] + (dp1[i + 1][j - n1] if j >= n1 else 0)

        @functools.lru_cache(None)
        def dfs1(i, nn, pp):
            # 处理已经遍历到答案的情况
            if i == size:
                if pp <= 0:
                    return 1
                else:
                    return 0

            # 剪枝1：如果当前人数不足以完成当前任务，那么也一定不足以完成之后的任务（按人数排序的任务列表）
            if nn < groups[i][0]:
                if pp <= 0:
                    return 1
                else:
                    return 0

            # 剪枝2：如果当前任务已经完成，则直接添加后面不考虑利润，只考虑人数的选择数
            if pp <= 0:
                return dp1[i][nn]

            res = 0
            res += dfs1(i + 1, nn, pp)  # 不完成当前任务
            res += dfs1(i + 1, nn - groups[i][0], pp - groups[i][1])  # 完成当前任务
            return res % MOD

        return dfs1(0, n, p)


if __name__ == "__main__":
    print(Solution().profitableSchemes(n=5, p=3, group=[2, 2], profit=[2, 3]))  # 2
    print(Solution().profitableSchemes(n=10, p=5, group=[2, 3, 5], profit=[6, 7, 8]))  # 7

    # 测试用例3
    print(Solution().profitableSchemes(n=1, p=1, group=[2, 2, 2, 2, 2], profit=[1, 2, 1, 1, 0]))  # 0
